Problem statement: zenit16cka

Alica v krajine fraktálov

Počet bodov: 50, časový limit: 5000ms

Alica už bola naozaj unavená zo všetkého toho ničnerobenia, sediac pri svojej sestre na brehu rieky a nemajúc nič na robote. Aj sa pokúšala niekoľkokrát nazrieť do knižky, ktorú si jej sestra čítala, ale keďže v knihe neboli žiadne obrázky, rýchlo ju to omrzelo. Veď na čo je taká knižka, ktorá v sebe nemá ani len obrázky?

Vo svojej letargii už začínala uvažovať, či stojí za to, zdvihnúť sa a spraviť si aspoň venček zo sedmokrások. Náhly pohyb odvedľa okamžite upútal jej pozornosť. V sestrinej knihe sa totiž objavil záhadný obrázok. Ešte záhadnejšie na ňom bolo, že sa pomaly hýbal a zväčšoval. A to tiež podivuhodným spôsobom.

Úloha

V tejto úlohe sa budeme zaoberať tými istými fraktálmi, s ktorými ste sa mohli stretnúť na krajskom kole. Vašou úlohou bude vo fraktáli nájsť niekoľko políčok, na ktorých budú mriežky.

Ďalej si pripomenieme, ako fungovali fraktály. Oproti zadaniu krajského kola sa zmenia iba dve maličkosti; namiesto znaku medzery budeme používať znak . a vzory budú vo všeobecnosti obdĺžnikové.

Fraktály sú obrazce, resp. obdĺžnikové tabuľky, pozostávajúce z mriežok (#) a bodiek (.). Fraktály budeme charakterizovať pomocou vzoru, čiže nejakého základného fraktálu rozmerov \(r \times c\), a čísla generácie \(n\).

Za fraktál nultej generácie označíme tabuľku \(1 \times 1\) obsahujúcu jedinú mriežku. Fraktál ľubovoľnej väčšej generácie \(n\) získame z fraktálu \((n-1)\)-vej generácie tak, že každé políčko expandujeme na tabuľku \(r \times c\). Ak sa na políčku pôvodne nachádzala mriežka, expandovaná tabuľka bude vzor fraktálu; ak sa na políčku nachádzala bodka, expandovaná tabuľka bude obsahovať samé bodky.

Na jednoduchom príklade si ukážeme niekoľko prvých generácií fraktálu so vzorkou:

#.#
.#.

Nultá generácia:

#

Prvá generácia:

#.#
.#.

Druhá generácia:

#.#...#.#
.#.....#.
...#.#...
....#....

Tretia generácia:

#.#...#.#.........#.#...#.#
.#.....#...........#.....#.
...#.#...............#.#...
....#.................#....
.........#.#...#.#.........
..........#.....#..........
............#.#............
.............#.............

Vstup a výstup

Na prvom riadku vstupu dostanete čísla \(r, c, n, k\) \((1 \leq r, c \leq 10, 1 \leq n \leq 200\,000, 1 \leq k \leq 100)\), počet riadkov a stĺpcov vzoru, číslo generácie a počet políčok s mriežkou, ktoré máte nájsť.

Ďalších \(r\) riadkov bude obsahovať popis vzoru.

Na výstup budete vypisovať súradnice políčok obsahujúcich mriežku. Ak je týchto políčok aspoň \(k\), môžete si vybrať ľubovoľných rôznych \(k\) políčok. V opačnom prípade vypíšte súradnice všetkých políčok s mriežkou.

Na prvý riadok vypíšte počet políčok \(q\), ktoré chcete vypísať. V každom z ďalších \(q\) riadkov vypíšte súradnice jedného políčka obsahujúceho mriežku, ako dvojicu čísel, kde prvá z nich bude číslo riadku a druhá číslo stĺpca. Riadky aj stĺpce číslujeme od nuly. Všetky vypísané súradnice musia byť navzájom rôzne.

Bodovanie a dobré rady do života

Za riešenie vypĺňajúce celý fraktál neočakávajte viac, než \(10\) bodov.

Za riešenie, ktoré si poradí s číslom generácie okolo \(1000\) môžete získať zhruba \(30\) bodov.

Vypisované čísla (a teda čísla, s ktorými budete pracovať) budú veľké, a tým myslíme naozaj veľké. Je odporúčané nesnažiť sa programovať vlastné veľké čísla, keďže pravdepodobne nebudú mať spravené dostatočne rýchle násobenie (prípadne delenie).

 Príklad

Input:

3 4 2 40
.##.
....
.##.

Output:

16
0 5
0 6
0 9
0 10
2 5
2 6
 ... Zvysok si domyslite ...

Celý fraktál si môžete pozrieť na obrázku dole. Keďže mriežok sa v ňom nachádza \(16\), vypíšeme iba tie.

.....##..##.....
................
.....##..##.....
................
................
................
.....##..##.....
................
.....##..##.....